package cn.cxq.learning.search;

/**
 * 插值查找，二分查找的优化
 */
public class InterpolationSearch {

    public static int recurSearch(int[] arr, int value) {

        int left = 0;
        int right = arr.length - 1;

        return itemSearch(arr, value, left, right);
    }

    private static int itemSearch(int[] arr, int value, int left, int right) {
        if (left > right) {
            return -1;
        }
        //int类型的乘除法一定要维持原顺序，不然的话中间的舍入会造成严重的结果不一致问题（不要觉得乘除法优先级相同就可以肆意调换顺序）
        int index = left + (right - left) * ((value - arr[left]) / (arr[right] - arr[left]));
        if (value == arr[index]) return index;
        else if (value > arr[index]) return itemSearch(arr, value, index + 1, right);
        else return itemSearch(arr, value, left, index - 1);
    }

    public static int search(int[] arr, int value) {

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {

            int index = left + (right - left) * ((value - arr[left]) / (arr[right] - arr[left]));

            if (value == arr[index]) return index;
            else if (value > arr[index]) left = index + 1;
            else right = index - 1;
        }

        return -1;
    }
}
